package datastructure.unionfind;

class 省份数量_547 {
    public int findCircleNum(int[][] isConnected) {
        UnionFind find = new UnionFind(isConnected.length);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = i + 1; j < isConnected.length; j++) {
                if (isConnected[i][j] == 1) {
                    find.union(i, j);
                }
            }

        }
        return find.size;
    }

    private class UnionFind {
        private final int[] root;
        private int size; // 集合数量

        /**
         * @param n n 个节点 记录每个节点的根是谁
         *          默认赋值都是孤立的
         */
        private UnionFind(int n) {
            root = new int[n];
            int i = 0;
            while (i < n) {
                root[i] = i++;
            }
            this.size = n;
        }


        public void union(int p, int q) {
            int pRoot = findRoot(p);
            int qRoot = findRoot(q);
            // 合并两个节点的根 孤岛减少一个
            if (pRoot != qRoot) {
                // 如果不修改根节点合并 而是把当前节点合并过去 root[q] = pRoot;
                //  根节点会成为孤岛 导致 连通分量个数+1  结果不准确
                root[qRoot] = pRoot;
                // 压缩到根节点的路径长度为2
                findRoot(q);
                this.size--;
            }
        }

        /**
         * @param p
         * @return root
         * 找到节点p的 根节点  根节点  就是未改变过的  初始赋值节点
         */
        private int findRoot(int p) {
            if (root[p] == p) {
                return p;
            }
            // 级联修改  遍历路径上每个都改
            // 同时压缩节点到根节点的值路径长度为2  直接root[p] 指向根节点 而不是一直转
            return root[p] = findRoot(root[p]);
        }
    }

}